//3
// 746. 使用最小花费爬楼梯
// https://leetcode.cn/problems/min-cost-climbing-stairs/
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        //动态规划
        //dp表 dp[i]:表示到达第i个台阶的最少花费
        vector<int> dp(1001,0);
        //初始化
        dp[0]=0;
        dp[1]=0;
        //自左向右填充dp表
        int end=cost.size();
        for(int i=2;i<=end;i++)
        {
            dp[i]=dp[i-1]+cost[i-1]<dp[i-2]+cost[i-2]
            ?dp[i-1]+cost[i-1]
            :dp[i-2]+cost[i-2];
        }
        return dp[end];
    }
};

// 91. 解码方法
// https://leetcode.cn/problems/decode-ways/
class Solution {
public:
    int numDecodings(string s) 
    {
        //在之前的基础上加数字，如果111+0形式那么111+0的解码方法为0
        //dp表，dp[i]表示以i为结尾的解码方法个数
        vector<int> ans(s.size(),0);
        //初始化dp[0]
        if(s[0]>='1'&&s[0]<='9')
        {
            ans[0]=1;
        }
        if(s.size()==1)
        {
            return ans[0];
        }
        //初始化dp[1]
        if(s[1]>='1'&&s[1]<='9')
        {
            ans[1]+=ans[0];
        }
        int num=(s[0]-'0')*10+(s[1]-'0');
        if(num>=10&&num<=26)
        {
            ans[1]++;
        }
        //填表
         for(int i=2;i<s.size();i++)
         {
             //单个元素
             if(s[i]>='1'&&s[i]<='9')
             {
                 ans[i]+=ans[i-1];
             }
             //组合元素
             num=(s[i-1]-'0')*10+(s[i]-'0');
             if(num>=10&&num<=26)
             {
                 ans[i]+=ans[i-2];
             }
         }
        //  for(auto ch:ans)
        //  {
        //      cout<<ch<<endl;
        //  }
         return ans[s.size()-1];
    }
};
